segment tree
Given a sequence of a fixed number of values, operations can be performed on that interval in logarithmic time data structure. Occurs quite frequently in AtCoder
Update value O(logN)
Operation on interval O(logN)
For example, "sum of the interval" for addition, and "max of the interval" for max.
It is not possible to delete elements, but there is no harm in doing so, since the sum can be updated with 0 instead of deletion, and the minimum value can be updated with a sufficiently large number.
An efficient way to find the minimum value is heapq, but since this one is random access and updates are not straightforward, the approach is to achieve deletion by skipping over invalid values. My implementation
→ Later make a version with segmented trees.
---
This page is auto-translated from /nishio/セグメント木. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I'm very happy to spread my thought to non-Japanese readers.